

import java.util.List;
import java.util.Random;
import java.util.Vector;

class FixNum {						//DESCRIZIONE TIPO DI DATO PER IDENTIFICARE LA CASELLA
	public int row;					//CON RIGA COLONNA E NUMERO CORRISPONDENTE
	public int column;				
	public int num;
	
	public FixNum(int row, int column, int num) {
		this.row = row;
		this.column = column;
		this.num = num;
	}
}

public class Sudoku {
	private static boolean checkValidity(int matrix[][], int minigrid_size, int sudoku_size) {	//METODO CHE CONTROLLA LA 
		// check rows									VALIDITA' DEL SUDOKU, SE RISPETTA VINCOLI
		for (int i=0; i<sudoku_size; ++i) {						// DELLE RIGHE, COLONNE, QUADRATI INTERNI
			for (int j=0; j<sudoku_size; ++j) {					//UNA VOLTA INSERITI I DATI
				for (int k=j+1; k<sudoku_size; ++k) {					
					if (matrix[i][j]==matrix[i][k])
						return false;
				}
			}
		}
		
		// check columns
		for (int i=0; i<sudoku_size; ++i) {
			for (int j=0; j<sudoku_size; ++j) {
				for (int k=i+1; k<sudoku_size; ++k) {
					if (matrix[i][j]==matrix[k][j])
						return false;
				}
			}
		}
		
		// check grids
		for (int i=0; i<sudoku_size; ++i) {
			for (int j=0; j<sudoku_size; ++j) {
				for (int ki=(i/minigrid_size)*minigrid_size; ki<((i+minigrid_size)/minigrid_size)*minigrid_size; ++ki) {
					for (int kj=(j/minigrid_size)*minigrid_size; kj<((j+minigrid_size)/minigrid_size)*minigrid_size; ++kj) {
						if (i==ki && j==kj)
							continue;	//MA NON È COME METTERE UN SALTO NEL CODICE? ...PROGRAMMAZIONE BRUTTA...
						if (matrix[i][j]==matrix[ki][kj])
							return false;
					}					
				}
			}
		}
		
		return !checkDuplicates(matrix, minigrid_size, sudoku_size); //RIFA TUTTI I CONTROLLI?
	}
	
	public static boolean checkValidity(int matrix[][]) { //CONTROLLA SE LA MATRICE È INIZIALIZZATA CORRETTAMENTE
		if (matrix==null)
			return false;
		if (matrix[0]==null)
			return false;
		if (matrix.length!=matrix[0].length)
			return false;

		int sudoku_size = matrix.length; 
		double double_minigrid_size = Math.sqrt(matrix.length);
		if (Double.valueOf(Math.pow(double_minigrid_size, 2)).intValue()!=sudoku_size)
			return false;
		int minigrid_size = Double.valueOf(double_minigrid_size).intValue();
		return checkValidity(matrix, minigrid_size, sudoku_size); //CHIAMA IL CONTROLLO SULLA MATRICE CON I DATI INSERITI (RIGA 18) 
	}
	
	
	private static boolean checkDuplicates(int matrix[][], int minigrid_size, int sudoku_size) { // CONTROLLA CHE NON CI SIANO VALORI 
		// check rows										DUPPLICATI SULLA STESSA:
		for (int i=0; i<sudoku_size; ++i) {
			for (int j=0; j<sudoku_size; ++j) {
				for (int k=j+1; k<sudoku_size; ++k) {
					if (matrix[i][j]!=0 && matrix[i][j]==matrix[i][k])
						return true;
				}
			}
		}
		
		// check columns
		for (int i=0; i<sudoku_size; ++i) {
			for (int j=0; j<sudoku_size; ++j) {
				for (int k=i+1; k<sudoku_size; ++k) {
					if (matrix[i][j]!=0 && matrix[i][j]==matrix[k][j])
						return true;
				}
			}
		}
		
		// check grids
		for (int i=0; i<sudoku_size; ++i) {
			for (int j=0; j<sudoku_size; ++j) {
				for (int ki=(i/minigrid_size)*minigrid_size; ki<((i+minigrid_size)/minigrid_size)*minigrid_size; ++ki) {
					for (int kj=(j/minigrid_size)*minigrid_size; kj<((j+minigrid_size)/minigrid_size)*minigrid_size; ++kj) {
						if (i==ki && j==kj)
							continue;
						if (matrix[i][j]!=0 && matrix[i][j]==matrix[ki][kj])
							return true;
					}					
				}
			}
		}
		
		return false;
	}
	
	private static int[][] solveSudoku(int m[][], List<Integer> p[][], int minigrid_size, int sudoku_size, FixNum fixNum) {
		// copy of matrix and possible
		int matrix[][] = new int[sudoku_size][sudoku_size];
		List<Integer> possible[][] = new List[sudoku_size][sudoku_size];
		for (int i=0; i<sudoku_size; ++i) {
			for (int j=0; j<sudoku_size; ++j) {
				matrix[i][j] = m[i][j];//COPPIA LA MATRICE
				possible[i][j] = new Vector<Integer>();//CREA UN VETTORE PER OGNI CELLA DELLA MATRICE
				if (matrix[i][j]==0)
					possible[i][j].addAll(p[i][j]); //SE LA CELLA È VUOTA METTE I VALORI POSSIBILI 0-9 NEL VETTORE
			}
		}
		// fix a number (only if brute force has been reached)
		if (fixNum!=null) {
			matrix[fixNum.row][fixNum.column]=fixNum.num;// ASSEGNA IL VALORE
			possible[fixNum.row][fixNum.column].clear();//ELIMINA IL VETTORE CHE CONTENEVA I POSSIBILI VALORI
		}
		
		while (true) {
			// check if sudoku has been solved	//È RISOLTO?
			boolean finish = true;
			for (int i=0; i<sudoku_size && finish; ++i) {
				for (int j=0; j<sudoku_size && finish; ++j) {
					if (matrix[i][j]==0)
						finish=false;
				}
			}

			// if sudoku has been solved check validity
			if (finish) {
				if (checkValidity(matrix, minigrid_size, sudoku_size)) //CONTROLLO CHE SIA STATO RISOLTO CORRETTAMENTE
					return matrix;
				return null;
			}
			
			
			boolean cont = false;	// true when a number is fixed
			
			// ROWS, COLUMNS, GRIDS (RCG)
			// check row, removes matrix[i][k] from the row matrix[i][j]
			for (int i=0; i<sudoku_size && !cont; ++i) {			//CONTROLLO SE MANCA UN SOLO VALORE 
				for (int j=0; j<sudoku_size && !cont; ++j) {		//DA AGGIUNGERE ALLA RIGA
					if (matrix[i][j]!=0)
						continue;
					for (int k=0; k<sudoku_size && !cont; ++k) {
						if (k==j || matrix[i][k]==0)
							continue;
						possible[i][j].remove((Integer)matrix[i][k]);
						if (possible[i][j].size()==0)
							return null;
						else if (possible[i][j].size()==1) {  
							matrix[i][j] = possible[i][j].remove(0);
							cont = true;
						}
					}
				}
			}
			if (cont) continue;

			// check column, removes matrix[k][j] from matrix[i][j]
			for (int i=0; i<sudoku_size && !cont; ++i) {			//CONTROLLO SE MANCA UN SOLO NUMERO
				for (int j=0; j<sudoku_size && !cont; ++j) {		//SULLA COLONNA
					if (matrix[i][j]!=0)
						continue;
					for (int k=0; k<sudoku_size && !cont; ++k) {
						if (k==i || matrix[k][j]==0)
							continue;
						possible[i][j].remove((Integer)matrix[k][j]);
						if (possible[i][j].size()==0)
							return null;
						else if (possible[i][j].size()==1) {
							matrix[i][j] = possible[i][j].remove(0);
							cont = true;
						}
					}
				}
			}
			if (cont) continue;
			
			// check grid, removes matrix[ki][kj] from matrix[i][j]
			for (int i=0; i<sudoku_size && !cont; ++i) {			//CONTROLLO SE MANCA UN SOLO NUMERO NEL QUADRATO INTERNO
				for (int j=0; j<sudoku_size && !cont; ++j) {
					if (matrix[i][j]!=0)
						continue;
					for (int ki=(i/minigrid_size)*minigrid_size; ki<((i+minigrid_size)/minigrid_size)*minigrid_size && !cont; ++ki) {
						for (int kj=(j/minigrid_size)*minigrid_size; kj<((j+minigrid_size)/minigrid_size)*minigrid_size && !cont; ++kj) {
							if ((ki==i && kj==j) || matrix[ki][kj]==0)
								continue;
							
							possible[i][j].remove((Integer)matrix[ki][kj]);
							if (possible[i][j].size()==0)
								return null;
							else if (possible[i][j].size()==1) {
								matrix[i][j] = possible[i][j].remove(0);
								cont = true;
							}
						}
					}
				}
			}
			if (cont) continue;
			
			
			// SEARCHING FOR LONE RANGERS	//CERCA "CAVALIERI SOLITARI" ??? o.O ???
			// check for lone rangers in rows
			for (int i=0; i<sudoku_size && !cont; ++i) {
				for (int j=0; j<sudoku_size && !cont; ++j) {
					if (matrix[i][j]!=0)
						continue;
					for (int num: possible[i][j]) {
						boolean alone = true;
						for (int k=0; k<sudoku_size; ++k) {
							if (k==j || matrix[i][k]!=0)
								continue;
							if (possible[i][k].contains((Integer)num)) {
								alone=false;
								break;
							}
						}
						if (alone) {
							matrix[i][j]=num;
							possible[i][j].clear();
							cont = true;
							break;
						}
					}
				}
			}
			if (cont) continue;
			
			// check for lone rangers in columns
			for (int i=0; i<sudoku_size && !cont; ++i) {
				for (int j=0; j<sudoku_size && !cont; ++j) {
					if (matrix[i][j]!=0)
						continue;
					for (int num: possible[i][j]) {
						boolean alone = true;
						for (int k=0; k<sudoku_size; ++k) {
							if (k==i || matrix[k][j]!=0)
								continue;
							if (possible[k][j].contains((Integer)num)) {
								alone=false;
								break;
							}
						}
						if (alone) {
							matrix[i][j]=num;
							possible[i][j].clear();
							cont = true;
							break;
						}
					}
				}
			}
			if (cont) continue;
			
			// check for lone rangers in grids
			for (int i=0; i<sudoku_size && !cont; ++i) {
				for (int j=0; j<sudoku_size && !cont; ++j) {
					if (matrix[i][j]!=0)
						continue;
					for (int num: possible[i][j]) {
						boolean alone = true;
						for (int ki=(i/minigrid_size)*minigrid_size; ki<((i+minigrid_size)/minigrid_size)*minigrid_size && alone; ++ki) {
							for (int kj=(j/minigrid_size)*minigrid_size; kj<((j+minigrid_size)/minigrid_size)*minigrid_size; ++kj) {
								if ((ki==i && kj==j) || matrix[ki][kj]!=0)
									continue;
								if (possible[ki][kj].contains((Integer)num)) {
									alone=false;
									break;
								}
							}
						}
						if (alone) {
							matrix[i][j]=num;
							possible[i][j].clear();
							cont = true;
							break;
						}
					}
				}
			}
			if (cont) continue;
			

			// SEARCHING FOR TWINS		//RICERCA PER GEMELLI ???o.O???
			// check for twins in rows
			Vector<Integer> indexes = new Vector<Integer>();
			for (int n=2; n<=4 && !cont; ++n) {
				for (int i=0; i<sudoku_size && !cont; ++i) {
					for (int j=0; j<sudoku_size && !cont; ++j) {
						if (matrix[i][j]!=0)
							continue;
						
						indexes.clear();
						indexes.add(j);
						for (int k=0; k<sudoku_size; ++k) {
							if (k==j || matrix[i][k]!=0)
								continue;
							if (possible[i][j].size()==n && possible[i][j].containsAll(possible[i][k])) {
								// twins found
								indexes.add(k);
								if (indexes.size()==n) {
									for (int l=0; l<sudoku_size; ++l) {
										if (indexes.contains(l))
											continue;
										if (possible[i][l].removeAll(possible[i][j]))
											cont = true;
									}
									for (int l=0; l<sudoku_size; ++l) {
										if (l==k || l==j)
											continue;
										if (matrix[i][l]==0) {
											if (possible[i][l].size()==0)
												return null;
											else if (possible[i][l].size()==1) {
												matrix[i][l] = possible[i][l].remove(0);
												cont = true;
											}
										}
									}
								}
							}
						}
					}
				}
			
				// check for twins in columns
				for (int i=0; i<sudoku_size && !cont; ++i) {
					for (int j=0; j<sudoku_size && !cont; ++j) {
						if (matrix[i][j]!=0)
							continue;
						
						indexes.clear();
						indexes.add(i);
						for (int k=0; k<sudoku_size; ++k) {
							if (k==i || matrix[k][j]!=0)
								continue;
							if (possible[i][j].size()==n && possible[i][j].containsAll(possible[k][j])) {
								// twins found
								indexes.add(k);
								if (indexes.size()==n) {
									for (int l=0; l<sudoku_size; ++l) {
										if (indexes.contains(l))
											continue;
										if (possible[l][j].removeAll(possible[i][j]))
											cont = true;
									}
									for (int l=0; l<sudoku_size; ++l) {
										if (l==k || l==i)
											continue;
										if (matrix[l][j]==0) {
											if (possible[l][j].size()==0)
												return null;
											else if (possible[l][j].size()==1) {
												matrix[l][j] = possible[l][j].remove(0);
												cont = true;
											}
										}
									}
								}
							}
						}
					}
				}

				// check for twins in grids
				for (int i=0; i<sudoku_size && !cont; ++i) {
					for (int j=0; j<sudoku_size && !cont; ++j) {
						if (matrix[i][j]!=0)
							continue;
						
						indexes.clear();
						indexes.add(i*sudoku_size+j);
						for (int ki=(i/minigrid_size)*minigrid_size; ki<((i+minigrid_size)/minigrid_size)*minigrid_size; ++ki) {
							for (int kj=(j/minigrid_size)*minigrid_size; kj<((j+minigrid_size)/minigrid_size)*minigrid_size; ++kj) {
								if ((ki==i && kj==j) || matrix[ki][kj]!=0)
									continue;
								if (possible[i][j].size()==n && possible[i][j].containsAll(possible[ki][kj])) {
									// twins found
									indexes.add(ki*sudoku_size+kj);
									if (indexes.size()==n) {
										for (int li=(i/minigrid_size)*minigrid_size; li<((i+minigrid_size)/minigrid_size)*minigrid_size; ++li) {
											for (int lj=(j/minigrid_size)*minigrid_size; lj<((j+minigrid_size)/minigrid_size)*minigrid_size; ++lj) {
												if (indexes.contains(li*sudoku_size+lj))
													continue;
												if (possible[li][lj].removeAll(possible[i][j]))
													cont = true;
											}
										}
										for (int li=(i/minigrid_size)*minigrid_size; li<((i+minigrid_size)/minigrid_size)*minigrid_size; ++li) {
											for (int lj=(j/minigrid_size)*minigrid_size; lj<((j+minigrid_size)/minigrid_size)*minigrid_size; ++lj) {
												if ((li==i && lj==j) || (li==ki && lj==kj))
													continue;
												if (matrix[li][lj]==0) {
													if (possible[li][lj].size()==0)
														return null;
													else if (possible[li][lj].size()==1) {
														matrix[li][lj] = possible[li][lj].remove(0);
														cont = true;
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
			if (cont) continue;
			
			
			// SEARCH FOR POSSIBILITIES JUST IN A ROW/COLUMN IN A MINIGRID CONTINUA A CERCARE POSSIBILITÀ... ???O.o???
			// searching for rows
			for (int i=0; i<sudoku_size; ++i) {	// row
				for (int j=0; j<sudoku_size; ++j) {	// columns
					for (int n: possible[i][j]) {
						boolean delete = true;
						for (int jj=0; jj<sudoku_size; ++jj) {
							if (j/minigrid_size==jj/minigrid_size)	// same row - same minigrid
								continue;
							if (possible[i][jj].contains((Integer)n)) {
								delete = false;
								break;
							}
						}
						if (delete) {
							int rowStart = (i/minigrid_size)*minigrid_size;
							int colStart = (j/minigrid_size)*minigrid_size;
							for (int ii=rowStart; ii<rowStart+minigrid_size; ++ii) {
								if (ii==i)
									continue;
								for (int jj=colStart; jj<colStart+minigrid_size; ++jj) {
									if (possible[ii][jj].size()==1) {
										matrix[ii][jj] = possible[ii][jj].remove(0);
										cont = true;
									}
								}
							}
						}
					}
				}
			}
			if (cont) continue;

			// searching for columns
			for (int i=0; i<sudoku_size; ++i) {	// row
				for (int j=0; j<sudoku_size; ++j) {	// columns
					for (int n: possible[i][j]) {
						boolean delete = true;
						for (int ii=0; ii<sudoku_size; ++ii) {
							if (i/minigrid_size==ii/minigrid_size)	// same column - same minigrid
								continue;
							if (possible[ii][j].contains((Integer)n)) {
								delete = false;
								break;
							}
						}
						if (delete) {
							int rowStart = (i/minigrid_size)*minigrid_size;
							int colStart = (j/minigrid_size)*minigrid_size;
							for (int jj=colStart; jj<colStart+minigrid_size; ++jj) {
								if (jj==j)
									continue;
								for (int ii=rowStart; ii<rowStart+minigrid_size; ++ii) {
									if (possible[ii][jj].size()==1) {
										matrix[ii][jj] = possible[ii][jj].remove(0);
										cont = true;
									}
								}
							}
						}
					}
				}
			}
			if (cont) continue;
			

			// BRUTE FORCE		
			int minAlt = sudoku_size+1;
			int yAlt = -1;
			int xAlt = -1;
			for (int i=0; i<sudoku_size; ++i) {
				for (int j=0; j<sudoku_size; ++j) {
					if (matrix[i][j]!=0)
						continue;
					if (possible[i][j].size()<minAlt) {
						minAlt = possible[i][j].size();
						yAlt = i;
						xAlt = j;
					}
				}
			}
			if (possible[yAlt][xAlt].size()==1) {
				matrix[yAlt][xAlt] = possible[yAlt][xAlt].remove(0);
				continue;
			}
			for (int k=possible[yAlt][xAlt].size()-1; k>=0; --k) {
				FixNum fix = new FixNum(yAlt, xAlt, possible[yAlt][xAlt].remove(k));
				int[][] solution = solveSudoku(matrix, possible, minigrid_size, sudoku_size, fix);
				if (solution!=null)
					return solution;
			}
		}
	}//FINE METODO SOLVESUDOKU
	
	public static int[][] generateSudoku(int minigrid_size) { //INIZIALIZZA LA MATRICE CHE DOVRÀ 
		int sudoku_size = minigrid_size*minigrid_size;    //CONTENERE IL SUDOKU
		int matrix[][] = new int[sudoku_size][sudoku_size];
		for (int i=0; i<sudoku_size; ++i) {
			for (int j=0; j<sudoku_size; ++j) {
				matrix[i][j] = 0;
			}
		}
		Vector<Integer> possible[][] = new Vector[sudoku_size][sudoku_size]; //INIZIALIZZA I VETTORI CON I POSSIBILI VALORI
		Random r = new Random(System.currentTimeMillis());
		for (int i=0; i<sudoku_size; ++i) {
			for (int j=0; j<sudoku_size; ++j) {
				possible[i][j] = new Vector<Integer>();
				for (int k=1; k<=sudoku_size; ++k) {
					int rand = r.nextInt(k);
					possible[i][j].add(rand, k);
				}
			}
		}

		int solution[][] = solveSudoku(matrix, possible, minigrid_size, sudoku_size, null);
		return solution;
	}
	
	public static int[][] solveSudoku(int matrix[][]) { // RICONTROLLO SE LA MATRICE
		if (matrix==null)			//È VALIDA O MENO
			return null;
		if (matrix[0]==null)
			return null;
		if (matrix.length!=matrix[0].length)
			return null;

		int sudoku_size = matrix.length;
		double double_minigrid_size = Math.sqrt(matrix.length);
		if (Double.valueOf(Math.pow(double_minigrid_size, 2)).intValue()!=sudoku_size)
			return null;
		int minigrid_size = Double.valueOf(double_minigrid_size).intValue();
		return solveSudoku(matrix, null, minigrid_size, sudoku_size, null);		
	}
}

class SudokuSolver{//MAIN 
	public static void main(String[] args){
		Sudoku su = new Sudoku();
		
		int[][] matrix = su.generateSudoku(3); //INDICA LA DIMENSIONE DEL QUADRATO INTERNO
		
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				System.out.print(matrix[i][j]+" ");
			}
			System.out.println("");
		}
		
		System.out.println("");
	}
}
